// https://leetcode.cn/problems/word-break/description/

// 算法思路总结：
// 1. 使用动态规划判断字符串能否被字典分割
// 2. dp[i]表示前i个字符能否被成功分割
// 3. 遍历所有分割点，检查字典包含子串
// 4. 时间复杂度：O(n²)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <bitset>

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        int m = s.size(), n = wordDict.size();
        s = " " + s;
        
        unordered_set<string> us;
        for (const string& str : wordDict)
            us.insert(str);

        bitset<301> dp;
        dp.set(0);

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= i ; j++)
            {
                if (dp[j - 1] && us.count(s.substr(j, i - j + 1)))
                {
                    dp.set(i);
                    break;
                }
            }
        }

        return dp.test(m);
    }
};

int main()
{
    string s1 = "leetcode", s2 = "applepenapple";
    vector<string> v1 = {"leet", "code"}, v2 = {"apple", "pen"};
    
    Solution sol;

    cout << sol.wordBreak(s1, v1) << endl;
    cout << sol.wordBreak(s2, v2) << endl;

    return 0;
}